package filter;

public class RulesChecker {

	String task;
	int[] opp;
	int[] sta;
	int rules_len;
	char[] rules;
	int flag = 1;
	boolean[] chg;
	
	void make_opp() {
		opp = new int[rules_len + 1];
		int tot = 0, top = 0;		
		
		for (int i = 0; i < rules_len; i++) {
			if (rules[i] == '"') {
				tot++;
			}
			if (tot % 2 == 0) {
				if (rules[i] == '(') 			
					sta[top++] = i;
				
				if (rules[i] == ')') {
					opp[i] = sta[top - 1];
					opp[sta[top - 1]] = i;
					top--;					
				}					
			}			
		}
		
	}
	
	int left_check(String t) {
		int tot = 0, top = 0, mx = 0;
		
		for (int i = 0; i < t.length(); i++) {
			if (t.charAt(i) == '"') tot++;
			if (tot % 2 == 0) {
				if (t.charAt(i) == '(')
					top++;
				if (t.charAt(i) == ')')
					top--;
				if (top < 0 && top < mx) mx = top;				
			}			
		}		
		return - mx;		
	}
	
	int right_check(String t) {
		int tot = 0, top = 0;
		
		for (int i = 0; i < t.length(); i++) {
			if (t.charAt(i) == '"') tot++;
			if (tot % 2 == 0) {
				if (t.charAt(i) == '(')
					top++;
				if (t.charAt(i) == ')')
					top--;								
			}			
		}
		return top;				
	}
	
	Boolean iscontain(String s, String t) {
		for (int i = 0; i < s.length(); i++) {
			int ok = 1;
			for (int j = 0; ok > 0 && j < t.length(); j++) {
				if (i + j >= s.length() || s.charAt(i + j) != t.charAt(j)) ok = 0; 	
			}			
			if (ok > 0) return true;
		}
		return false;
	}
	
	
	public Object[] make_it_correct(String tmp) {
		Boolean correct = true;
		int tot = 0;
		for (int i = 0; i < tmp.length(); i++) 
			if (tmp.charAt(i) == '"')
				tot++;
		if (tot % 2 != 0) {
			tmp = tmp + "\"";
			correct = false;
		}
		
		while (true) {
			int t = left_check(tmp);
			if (t == 0) break;
			for (int i = 0; i < t; i++) tmp = "(" + tmp;
			correct = false;
		}
		
		while (true) {
			int t = right_check(tmp);
			if (t == 0) break;
			for (int i = 0; i < t; i++) tmp = tmp + ")";
			correct = false;
		}
		int [] del = new int[tmp.length()];
		for (int i = 0; i < tmp.length(); i++) del[i] = 0;
		
		int top = 0;
		tot = 0; 
		Boolean head = true;
		for (int i = 0; i < tmp.length(); i++) {
			if (tmp.charAt(i) == '"') tot++;
			if (tot % 2 == 0) {
				if (tmp.charAt(i) == '(') {
					for (int k = i + 1; k < tmp.length(); k++) {
						if (tmp.charAt(k) != '(' && tmp.charAt(k) != ')' && tmp.charAt(k) != '"') {
							if (tmp.charAt(k) != ' ' && tmp.charAt(k) != '\t') correct = false;						
							del[k] = 1;
						}
						else break;
					}											
				}				
				if (tmp.charAt(i) == ')') {
					for (int k = i - 1; k >= 0; k--) {
						if (tmp.charAt(k) != '(' && tmp.charAt(k) != ')' && tmp.charAt(k) != '"') {
							if (tmp.charAt(k) != ' ' && tmp.charAt(k) != '\t') correct = false;						
							del[k] = 1;
						}
						else break;
					}																		
				}
			}
		}
		String ret = "";
		for (int i = 0; i < tmp.length(); i++) 
			if (del[i] == 0) {
				ret = ret + tmp.charAt(i);
			}
		
		tmp = ret;
		for (int i = 0; i < tmp.length(); i++) del[i] = 0;
		tot = 0; top = 0;
		for (int i = 0; i < tmp.length(); i++) {
			if (tmp.charAt(i) == '"') {
				tot++;
				continue;
			}
			if (tot % 2 == 0) {
				if (tmp.charAt(i) == '(') continue;
				if (tmp.charAt(i) == ')') continue;
				String nows = "";
				int k;
				for (k = i; k < tmp.length(); k++) {
					if (tmp.charAt(k) == '"') break;
					if (tmp.charAt(k) == '(') break;
					if (tmp.charAt(k) == ')') break;
					nows = nows + tmp.charAt(k);					 
				}				
				//System.out.println(nows);
				if (iscontain(nows, "and")) del[i] = 1;
				else if (iscontain(nows, "or")) del[i] = 2;
				else {
					if (iscontain(nows, "an")) del[i] = 1;
					if (iscontain(nows, "nd")) del[i] = 1;
					if (iscontain(nows, "ad")) del[i] = 1;
					if (iscontain(nows, "a")) del[i] = 1;
					if (iscontain(nows, "n")) del[i] = 1;
					if (iscontain(nows, "d")) del[i] = 1;
					if (iscontain(nows, "o")) del[i] = 2;
					if (iscontain(nows, "r")) del[i] = 2;
					if (del[i] > 0) correct = false;
				}
				if (nows != "") i = k - 1;
			}			
		}
		//System.out.println(tmp);
		ret = "";
		tot = 0;
		for (int i = 0; i < tmp.length(); i++) {
			if (tmp.charAt(i) == '"') {
				ret = ret + "\"";
				tot++;
				continue;
			}
			if (tot % 2 == 0) {				
				if (del[i] == 1) ret = ret + "and";
				if (del[i] == 2) ret = ret + "or";				
				if (tmp.charAt(i) == '(') ret = ret + "(";
				if (tmp.charAt(i) == ')') ret = ret + ")";				
			} else ret = ret + tmp.charAt(i);
		}
		Object [] R = new Object[2];
		R[0] = correct;
		
		R[1] = ret;
		
		return R;
	}
	
	public void set(String x) {
		if (x == null || x == "") {
			flag = 1;
			return;
		}
		String rule = x;
		int len = rule.length();
		
		String tmp = "";
		int now = 0;
		for (int i = 0; i < len; i++) {
			if (rule.charAt(i) == '\"') {
				now++;
				tmp = tmp + "\"";
				continue;
			}
			
			if (now % 2 == 0) {				
				if (rule.charAt(i) == 'a' && rule.charAt(i + 1) == 'n' && rule.charAt(i + 2) == 'd') {
					tmp = tmp + "*";
				}
				
				if (rule.charAt(i) == 'o' && rule.charAt(i + 1) == 'r') {
					tmp = tmp + "+";
				}
				
				if (rule.charAt(i) == '(') tmp = tmp + "(";
				if (rule.charAt(i) == ')') tmp = tmp + ")";														
			}
			if (now % 2 == 1) tmp = tmp + rule.charAt(i);
		}
		
		if (tmp == "") {
			flag = 1;
			return;
		} else flag = 0;
		
		rules_len = tmp.length();
		rules = tmp.toCharArray();
		sta = new int[rules_len + 1];
		make_opp();
	}

	int[] preProcess(String B) {
		int size = B.length();
		int[] P = new int[size];
		P[0] = 0;
		int j = 0;
		for (int i = 1; i < size; i++) {
			while (j > 0 && B.charAt(j) != B.charAt(i)) {
				j = P[j];
			}
			if (B.charAt(j) == B.charAt(i)) {
				j++;
			}
			P[i] = j;
		}
		return P;
	}

	Boolean kmp(String parStr, String subStr) {
		int subSize = subStr.length();
		int parSize = parStr.length();
		char[] B = subStr.toCharArray();
		char[] A = parStr.toCharArray();
		int[] P = preProcess(subStr);
		int j = 0;
		int k = 0;
		Boolean ret = false;
		for (int i = 0; i < parSize; i++) {
			while (j > 0 && B[j] != A[i]) {
				j = P[j - 1];
			}
			if (B[j] == A[i]) {
				j++;
			}
			if (j == subSize) {
				j = P[j - 1];
				k++;
				for (int w = 0; w < subStr.length(); w++) 
					chg[i - subSize + 1 + w] = true;
				ret = true;
				//return true; 
//				System.out.printf("Find subString '%s' at %d\n", subStr, i - subSize + 1);
			}
		}
		//System.out.printf("Totally found %d times for '%s'.\n\n", k, subStr);		
		return ret;
	}
	
	Boolean get(int l, int r) {
		if (rules[l] == '(' && rules[r] == ')' && opp[l] == r) {
			return get(l + 1, r - 1);
		}
		int k = -1, tot = 0;
		for (int i = l; i <= r; i++) {
			if (rules[i] == '(') tot++;
			if (rules[i] == ')') tot--;
			if (tot == 0 && rules[i] == '+') k = i;			
		}
		
		if (k >= 0) {
			Boolean ll = get(l, k - 1), rr = get(k + 1, r);
			return ll || rr;						
		}
		
		k = -1; tot = 0;
		for (int i = l; i <= r; i++) {
			if (rules[i] == '(') tot++;
			if (rules[i] == ')') tot--;
			if (tot == 0 && rules[i] == '*') k = i;			
		}
		if (k >= 0) {
			Boolean ll = get(l, k - 1), rr = get(k + 1, r);
			return ll && rr;										
		}
		
		if (rules[l] == '\"' && rules[r] == '\"') {
			String now = "";
			for (int i = l + 1; i < r; i++) now = now + rules[i];
			return kmp(task, now); 
		}
		
		return true;		
	}

	public Object[] check(String t) {
		task = t;
		if (flag == 1) {
			Object[] ret = new Object[1];
			ret[0] = false;
			return ret;
		}
		
		
		Object[] ret = new Object[2];
		chg = new boolean[t.length()];
		for (int i = 0; i < t.length(); i++) chg[i] = false;
		ret[0] = get(0, rules_len - 1);
		ret[1] = chg;
/*		System.out.println(t);
		for (int i = 0; i < t.length(); i++) 
			if (chg[i]) 
				System.out.print(t.charAt(i));
			else 
				System.out.print("*");
		System.out.println();
		*/
		return ret;
		
		//return get(0, rules_len - 1);
	}

	public static void main(String[] args) {
		RulesChecker rc = new RulesChecker();
		Object [] testcorrect = rc.make_it_correct("\"a\"and\"b\"");
		if ((Boolean) testcorrect[0]) System.out.println("yes"); else System.out.println("no");

//		RulesChecker.make_it_correct("\"nMcuAdrs=0x10301\" and \"CmdCode = 0x11ab\"");
		//System.out.println(rules);
		rc.set("\"nMcuAdrs=0x10301\" and \"CmdCode = 0x11ab\"");
		Object[] ret = rc.check("Ncp Send Message To Mcu:  nMcuAdrs=0x10301 CmdCode = 0x11ab,lParamLen = 0x12");
		if ((Boolean) ret[0])
			System.out.println("yes");
		else
			System.out.println("no");
	}

}
